package com.test.daily.leetcode.y2022.m06.day0616.v02;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/6/16 下午 07:29
 * @version: 1.0
 */
public class Solution {
    public static int[][] nearestLeft(int[] arr) {
        int[][] nearestLeft = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (stack.size() != 0 && arr[stack.peek()] > arr[i]) {
                int x = stack.pop();
                nearestLeft[x][0] = stack.isEmpty() ? -1 : stack.peek();
                nearestLeft[i][1] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int j = stack.pop();
            nearestLeft[j][0] = stack.isEmpty() ? -1 : stack.peek();
            nearestLeft[j][1] = -1;
        }
        return nearestLeft;
    }

    public static int[][] getNearestLeftIncludeRepeat(int[] arr) {
        int[][] leftNearest = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
                List<Integer> list = stack.pop();
                int leftest = stack.size() == 0 ? -1 : stack.peek().get(stack.peek().size() - 1);
                for(int index : list){
                    leftNearest[index][0] = leftest;
                    leftNearest[index][1] = i;
                }
            }
            if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){
                stack.peek().add(i);
            } else {
                List list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while(!stack.isEmpty()){
            List<Integer> list = stack.pop();
            int leftest = stack.isEmpty() ? -1: stack.peek().get(0);
            for(int index: list){
                leftNearest[index][0] = leftest;
                leftNearest[index][1] = -1;
            }
        }
        return leftNearest;
    }
}
